package simple.array;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-prefix-divisible-by-5/">1018. 可被 5 整除的二进制前缀</a>
 * 给定一个二进制数组 nums ( 索引从0开始 )。
 * 我们将xi 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。
 * 例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。
 * 返回布尔值列表 answer，只有当 xi 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
 * 示例 1：
 *   输入：nums = [0,1,1]
 *   输出：[true,false,false]
 *   解释：
 *     输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。
 * 示例 2：
 *   输入：nums = [1,1,1]
 *   输出：[false,false,false]
 * 提示：
 *   1 <= nums.length <= 10^5
 *   nums[i] 仅为 0 或 1
 * @author 刘学松
 * @date 2023-07-04 16:21
 */
public class 可被5整除的二进制前缀 {
    public static List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> list = new ArrayList<>();
        // needs1 表示val左移1位后对5取模的结果，needs2表示val左移1位+1后对5取模的结果，只要结果为0就表示可以被5整除
        int[] needs1 = new int[]{0, 2, 4, 1, 3};
        int[] needs2 = new int[]{1, 3, 0, 2, 4};
        int val = 0;
        for (int num : nums) {
            if (num == 0) {
                val = needs1[val];
            } else {
                val = needs2[val];
            }
            list.add(val == 0);
        }
        return list;
    }

    public static List<Boolean> prefixesDivBy51(int[] nums) {
        List<Boolean> list = new ArrayList<>();
        int val = 0;
        for (int num : nums) {
            val = (val) << 1 + num;
            val %= 5;
            list.add(val == 0);
        }
        return list;
    }
}
